/* much of this could be abstracted out, but I'm not sure that would not have performance 
* implications, and I'm very interested in speed.... so a little metaprogramming. -H 0904
*/

val nodes=List((2,"Two"),
	       (3,"Three"),
	       (4,"Four"),
	       (5,"Five"),
	       (6,"Six"),
	       (7,"Seven"),
	       (8,"Eight"),
	       (16,"Sixteen"),
	       (32,"ThirtyTwo"),
	       (64,"SixtyFour") // will you still feed me?
	 ); 
val lists=List((4,"Four"),
	       (8,"Eight"),
	       (16,"Sixteen"),
	       (32,"ThirtyTwo")
	 );

val fields={1 to 64 toList}.map("_"+_);
val elems={1 to 64 toList}.map(i => "e.next");
val cases={0 to 63 toList}.zip(fields).map{case (i,s) => "case "+i+" => "+s+"; "};
println("package org.thewares.collection.nodal;");
println("import org.thewares.collection.ReverseDeque;");
println("object Nodes {");

println("""  def yikes=throw new Error("Not yet supported");""");

for ((size, shortName) <- lists){
val name="LittleList"+shortName;

println("""
      case object Empty"""+name+""" extends EmptyDeck with SmallDeck[Nothing] {
	    def apply(n:Int):Nothing=error("element "+n+" is not in EmptyDeck"); 
	    def elements=Iterator.empty;
	    def reverseElements=Iterator.empty;
	    override def reverseDeque=this;
	    override def isEmpty=true;
	    def length=0;
	    
	    def +[B](elem: B):Deck[B]= new """+name+"""1(elem);
	    def peek:Nothing=error("EmptyDeck has no elements"); 
	    def pop:Deck[Nothing]=error("EmptyDeck has no elements"); 
	    
	    def ::[B](elem: B):Deck[B]=new """+name+"""1(elem);
	    def head: Nothing=error("EmptyDeck has no elements"); 
	    def tail: Deck[Nothing]=error("EmptyDeck has no elements"); 

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:Deck[_] => ed.length==0;
		  case _ => false;
	    }

	    def nodes=0;
	    def depth=0;
	    def state="0";
      }

	trait """+name+"""Front1[+A] extends SmallDeck[A]{};
	trait """+name+"""Back1[+A] extends SmallDeck[A]{def tl:A};
      final case class """+name+"""1[+A](hd:A) extends SmallDeck[A] with """+name+"""Back1[A] with """+name+"""Front1[A] {
	    def tl=hd;
	    def apply(n:Int):A= if (n==0) {hd} else error("element "+n+" is not in SingletonDeck");  
	    def length=1;
	    def elements=Iterator.single(hd);
	    def reverseElements=Iterator.single(hd);
	    override def isEmpty=false;
	    def toNode= new """+shortName+"""1(hd);
	    
	    def +[B >: A](elem: B)={
		  new """+name+"""Back2(this,elem);
	    }
	    def peek:A= hd;
	    def pop= Empty"""+name+""";
	    
	    def ::[B >: A](elem: B)={
		  new """+name+"""Front2(elem,this);
	    }
	    def head: A= hd;
	    def tail=Empty"""+name+""";
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="1";
	
            def :::[B>:A](that:Deque[B])={
		  if (that.size==0) {
			this 
		  } else {
			that match {
			      case other:Deck[B] => other + hd;
			      case _ => yikes;
			}
		  }
	    }

      } // 1
""");

for (j <- 2 to size){

      def tails(i:Int)={
	    { for (j <- 0 to i-1) yield "case "+j+" => "+List.make((j-1),"tl.").mkString + "hd; \n"}.mkString
      }
      def heads(i:Int)={
	    {for (j <- 0 to i-1)yield "case "+j+" => "+List.make(i-j-1,"hd.").mkString + "tl; \n"}.mkString
      }

println("""
	final case class """+name+"Front"+j+"[+A](hd:A, tl:"+name+"Front"+(j-1)+"""[A]) extends SmallDeck[A] {
	      self =>
	    def apply(n:Int):A= n match { """+tails(j)+""" 
	                                 case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length="""+j+""";
	    def elements={new Iterator[A]{ var ptr:Deck[A]=self;
	                               def hasNext= !ptr.isEmpty;
				       def next:A={
					     if (ptr.isEmpty) 
						   throw new NoSuchElementException("next on empty iterator");	    
					     else {
						   val ret=ptr.head; ptr=ptr.tail; ret;
					     }
				       }}};
	    def reverseElements=toNode.reverseElements;

	    def toNode= {val e=elements; new """+shortName+j+"("+List.make(j,"e.next").mkString(",")+""");};

	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= toNode + elem;

	    def peek:A= apply(length);
	    def pop= {val e=elements; new """+shortName+(j-1)+"("+List.make(j-1,"e.next").mkString(",")+""");};

	    def ::[B >: A](elem: B)= """ + {if (j<size) { 
		  """ new """+name+"Front"+(j+1)+"""(elem,this);"""
	    } else {
		  """ new DoubleDeck"""+shortName+"("+name+"""1(elem),this); """
	    }} + """
	    def head: A= hd;
	    def tail = tl;
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="""+ {if (j<size) "\"n\"" else "\"N\"" }+""";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => { val e=elements; // FIXME:  is this backwards?
			      """+ List.make(j,"e.next").mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => { val e=elements;
			          other + """+ elems.take(j).mkString("+") + """ 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n

      final case class """+name+"Back"+j+"[+A](hd:"+name+"Back"+(j-1)+"""[A],tl:A) extends SmallDeck[A] {
	    self =>
	    def apply(n:Int):A= n match { """+heads(j)+""" 
	                                 case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length="""+j+""";
	    def reverseElements=new Iterator[A]{ var ptr:Deck[A]=self;
	                               def hasNext= !ptr.isEmpty;
				       def next:A={
					     if (ptr.isEmpty) 
						   throw new NoSuchElementException("next on empty iterator");	    
					     else {
						   val ret=ptr.peek; ptr=ptr.pop; ret;
					     }
				       }};
	    def elements=toReverseNode.reverseElements;

	    def toReverseNode= {val e=reverseElements; 
				new """+shortName+j+"("+List.make(j,"e.next").mkString(",")+""");};
	    def toNode= {val e=elements; new """+shortName+j+"("+List.make(j,"e.next").mkString(",")+""");};

	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= """ + {if (j<size) {
		  """ new """+name+"Back"+(j+1)+"""(this,elem);"""
	    } else {
		  """ new DoubleDeck"""+shortName+"(this,"+name+"1(elem)); "
	    }} +"""
	    def peek:A= tl;
	    def pop= hd;

	    def ::[B >: A](elem: B)= elem :: toNode;
	    def head: A= apply(0);
	    def tail = toNode.tail;
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="""+ {if (j<size) "\"n\"" else "\"N\""}+""";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => { val e=elements; // FIXME:  is this backwards?
			      """+ List.make(j,"e.next").mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => { val e=elements;
			          other + """+ elems.take(j).mkString("+") + """ 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       }  //n
""");


}}

for ((size, name) <-nodes){
val caseModifier=if (size<=22) "case" else "";

println("""
      case object Empty"""+name+""" extends EmptyDeck {
	    def apply(n:Int):Nothing=error("element "+n+" is not in EmptyDeck"); 
	    def elements=Iterator.empty;
	    def reverseElements=Iterator.empty;
	    override def reverseDeque=this;
	    override def isEmpty=true;
	    def length=0;
	    
	    def +[B](elem: B):Deck[B]= new """+name+"""1(elem);
	    def peek:Nothing=error("EmptyDeck has no elements"); 
	    def pop:Deck[Nothing]=error("EmptyDeck has no elements"); 
	    
	    def ::[B](elem: B):Deck[B]=new """+name+"""1(elem);
	    def head: Nothing=error("EmptyDeck has no elements"); 
	    def tail: Deck[Nothing]=error("EmptyDeck has no elements"); 
	    

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:Deck[_] => ed.length==0;
		  case _ => false;
	    }

	    def nodes=0;
	    def depth=0;
	    def state="0";
      }
      
      final """+caseModifier+""" class """+name+"""1[+A](_1:A) extends SmallDeck[A] {
	    def apply(n:Int):A= if (n==0) {_1} else error("element "+n+" is not in SingletonDeck");  
	    def length=1;
	    def elements=Iterator.single(_1);
	    def reverseElements=Iterator.single(_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B):"""+name+"""2[B]={
		  new """+name+"""2(_1,elem);
	    }
	    def peek:A= _1;
	    def pop= Empty"""+name+""";
	    
	    def ::[B >: A](elem: B):"""+name+"""2[B]={
		  new """+name+"""2(elem,_1);
	    }
	    def head: A= _1;
	    def tail=Empty"""+name+""";
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="1";
	
            def :::[B>:A](that:Deque[B])={
		  if (that.size==0) {
			this 
		  } else {
			that match {
			      case other:Deck[B] => other + _1;
			      case _ => yikes;
			}
		  }
	    }

      } // 1

      final """+caseModifier+""" class """+name+size+"[+A]"+fields.take(size).mkString("(",":A, ",":A)")+""" extends SmallDeck[A] {
	    def apply(n:Int):A= n match { """+cases.take(size).mkString+"""case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length="""+size+""";
	    def elements=Iterator.fromValues("""+fields.take(size).mkString(",")+""");
	    def reverseElements=Iterator.fromValues("""+fields.take(size).reverse.mkString(",")+""");
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new DoubleDeck"""+name+"""(this,new """+name+"""1(elem));

	    def peek:A= """+fields(size-1)+""";
	    def pop= new """+name+(size-1)+"("+fields.take(size-1).mkString(",")+""");

	    def ::[B >: A](elem: B)= new DoubleDeck"""+name+"""(new """+name+"""1(elem),this);
	    def head: A= _1;
	    def tail:"""+name+(size-1)+"""[A] = new """+name+(size-1)+"("+fields.drop(1).take(size-1).mkString(",")+""");
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="N";

	    override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => {
			      """+ fields.take(size).mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + """+ fields.take(size).mkString("+") + """ 
			      }
	                      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      } //N
		 
""");
for (j<-2 to size-1){

println("""
      final """+caseModifier+""" class """+name+j+"[+a]"+fields.take(j).mkString("(",":a, ",":a)")+""" extends SmallDeck[a] {
	    def apply(n:Int):a= n match { """+cases.take(j).mkString+"""case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length="""+j+""";
	    def elements=Iterator.fromValues("""+fields.take(j).mkString(",")+""");
	    def reverseElements=Iterator.fromValues("""+fields.take(j).reverse.mkString(",")+""");
	    override def isEmpty=false;
	    
	    def +[b >: a](elem: b)= new """+name+(j+1)+"("+fields.take(j).mkString(",")+""",elem);

	    def peek:a= """+fields(j-1)+""";
	    def pop= new """+name+(j-1)+"("+fields.take(j-1).mkString(",")+""");

	    def ::[b >: a](elem: b)= new """+name+(j+1)+"(elem,"+fields.take(j).mkString(",")+""");
	    def head: a= _1;
	    def tail:"""+name+(j-1)+"""[a] = new """+name+(j-1)+"("+fields.drop(1).take(j-1).mkString(",")+""");
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: a](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => {
			      """+ fields.take(j).mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: a](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + """+ fields.take(j).mkString("+") + """ 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n
""");
}

println("""
      final case class DoubleDeck"""+name+"""[+A](front:Deck[A],back:Deck[A]) extends Deck[A] {
	    type DoubleDeck[+T]= DoubleDeck"""+name+"""[T];
	    type TripleDeck[+T]= TripleDeck"""+name+"""[T];
	    type SingletonDeck[+T]= """+name+"""1[T];
	    final private val EmptyDeck= Empty"""+name+""";

	    def apply(n: Int): A={
		  if (n<front.length){
			front.apply(n);
		  } else {
			back.apply(n-front.length);
		  }
	    }
	    
	    def elements: Iterator[A]= front.elements ++ back.elements;
	    def reverseElements: Iterator[A]= back.reverseElements ++ front.reverseElements;
	    override def isEmpty: Boolean= false;
	    def length:Int=front.length + back.length;

	    def +[B >: A](elem: B):Deck[B]={
		  if (back.length=="""+size+"""){
			new TripleDeck(length+1,front,new SingletonDeck(back),new SingletonDeck(elem)); //k
		  } else {
			new DoubleDeck(front,back.push(elem)); //k
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={ 
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			front;
		  } else {
			new DoubleDeck(front,postpop);
		  }
	    }
	    def ::[B >: A](elem: B):Deck[B]={
		  if (front.length=="""+size+"""){
			new TripleDeck(length+1,new SingletonDeck(elem),new SingletonDeck(front),back); //k
		  } else {
			new DoubleDeck(front.unshift(elem),back); //k
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val posttail=front.tail;
		  if (posttail.isEmpty){
			back;
		  } else {
			new DoubleDeck(posttail,back); //k
		  }
	    }

	    def nodes=1+front.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  1+ (if (fd>bd) fd else bd)
	    }
	    def state="["+front.state+","+back.state+"]";
	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  
		  that match{
			case EmptyDeck => this;
		       
			case _ => { // not optimized
			      throw new Error("Not yet supported:  "+that.getClass); // shouldn't be called yet. fixme			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    } // end :::
      } // DoubleDeck

      // none of these subdeques are empty
      final case class TripleDeck"""+name+"""[+A](N:Int,front:Deck[A],up:Deck[Deck[A]],back:Deck[A]) extends Deck[A] {
	    type DoubleDeck[+T]= DoubleDeck"""+name+"""[T];
	    type TripleDeck[+T]= TripleDeck"""+name+"""[T];
	    type SingletonDeck[+T]= """+name+"""1[T];
	    final private val EmptyDeck= Empty"""+name+""";
	    
	    // slow.
	    def apply(n: Int): A= elements.drop(n).next();
	    
	    // does Iterator.flatten make them less lazy?  Its best if they are not wasting memory.
	    def elements: Iterator[A]= front.elements ++ Iterator.flatten(up.map(_.elements).elements) ++ back.elements;
	    // this looks buggy, is It?
	    def reverseElements: Iterator[A]= {back.reverseElements ++ 
					       Iterator.flatten(up.reverseElements.map(_.reverseElements))++
					       front.reverseElements;}
	    override def isEmpty: Boolean= false;
	    def length:Int=N;
	    
	    def +[B >: A](elem: B):Deck[B]={
		  if (back.length=="""+size+"""){
			new TripleDeck(N+1,front,up.push(back),new SingletonDeck(elem));
		  } else {
			new TripleDeck(N+1,front,up,back.push(elem));
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			val uppop=up.pop;
			if (uppop.isEmpty){
			      new DoubleDeck(front,up.peek); 
			} else {
			      new TripleDeck(N-1,front, uppop, up.peek); 
			}
		  } else {
			new TripleDeck(N-1,front,up,postpop); 
		  }
	    }
	    
	    def ::[B >: A](elem: B):Deck[B]={
		  if (front.length=="""+size+"""){
			new TripleDeck(N+1,new SingletonDeck(elem),up.unshift(front),back);
		  } else {
			new TripleDeck(N+1,front.unshift(elem),up,back);
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val fronttail=front.tail;
		  if (fronttail.isEmpty){
			val uptail=up.tail;
			if (uptail.isEmpty){
			      new DoubleDeck(up.head,back)
			} else {
			      new TripleDeck(N-1,up.head,uptail,back);
			}
		  } else {
			new TripleDeck(N-1,fronttail,up,back);
		  }
	    }
	    def nodes=1+front.nodes+up.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  val mfb=if (fd>bd) fd else bd;
		  val ud=up.depth;
		  1+ (if (ud>mfb) ud else mfb);
	    }
	    def state="("+front.state+","+up.state+","+back.state+")";


	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case EmptyDeck => this;
			case other:SmallDeck[_] =>{
			      (other.asInstanceOf[Deck[B]] :\ this.asInstanceOf[Deck[B]]){case (e,d) => e::d}
			}
			case that:Deque[B] => { // not optimized
			      throw new Error("Not yet supported:  "+that.getClass); // shouldn't be called yet. fixme
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

      }// end TripleDeck


""");

}

// fnodes
for ((size, basename) <-nodes){
val caseModifier=if (size<=22) "case" else "";
val name="F"+basename;

println("""
      case object Empty"""+name+""" extends EmptyDeck {
	    def apply(n:Int):Nothing=error("element "+n+" is not in EmptyDeck"); 
	    def elements=Iterator.empty;
	    def reverseElements=Iterator.empty;
	    override def reverseDeque=this;
	    override def isEmpty=true;
	    def length=0;
	    
	    def +[B](elem: B):Deck[B]= new """+name+"""1(elem);
	    def peek:Nothing=error("EmptyDeck has no elements"); 
	    def pop:Deck[Nothing]=error("EmptyDeck has no elements"); 
	    
	    def ::[B](elem: B):Deck[B]=new """+name+"""1(elem);
	    def head: Nothing=error("EmptyDeck has no elements"); 
	    def tail: Deck[Nothing]=error("EmptyDeck has no elements"); 
	    

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:Deck[_] => ed.length==0;
		  case _ => false;
	    }

	    def nodes=0;
	    def depth=0;
	    def state="0";
      }
      
      final """+caseModifier+""" class """+name+"""1[+A](_1:A) extends SmallDeck[A] {
	    def apply(n:Int):A= if (n==0) {_1} else error("element "+n+" is not in SingletonDeck");  
	    def length=1;
	    def elements=Iterator.single(_1);
	    def reverseElements=Iterator.single(_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B):"""+name+"""2[B]={
		  new """+name+"""2(_1,elem);
	    }
	    def peek:A= _1;
	    def pop= Empty"""+name+""";
	    
	    def ::[B >: A](elem: B):"""+name+"""2[B]={
		  new """+name+"""2(elem,_1);
	    }
	    def head: A= _1;
	    def tail=Empty"""+name+""";
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="1";
	
            def :::[B>:A](that:Deque[B])={
		  if (that.size==0) {
			this 
		  } else {
			that match {
			      case other:Deck[B] => other + _1;
			      case _ => yikes;
			}
		  }
	    }

      } // 1

      final private val """+name+"F"+size+":Array[Function1["+name+size+"[_],_]]=Array"+
	fields.take(size).map{s => "(x:"+name+size+"[_]) => x."+s}.mkString("({","}, {","});")+"""
      final private val """+name+"F"+size+"Reversed:Array[Function1["+name+size+"[_],_]]="+name+"F"+size+""".reverse;

      final """+caseModifier+""" class """+name+size+"[+A]"+fields.take(size).mkString("(val ",":A, val ",":A)")+""" extends SmallDeck[A] {
	    def apply(n:Int):A= """++name+"F"+size +"""(n).asInstanceOf[A];
	    def elements="""++name+"F"+size+""".elements.map{f => f(this).asInstanceOf[A]};
	    def reverseElements="""++name+"F"+size+"""Reversed.elements.map{f => f(this).asInstanceOf[A]};
	    def length="""+size+""";

	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new DoubleDeck"""+name+"""[B](this,new """+name+"""1[B](elem));

	    def peek:A= """+fields(size-1)+""";
	    def pop= new """+name+(size-1)+"("+fields.take(size-1).mkString(",")+""");


	    def ::[B >: A](elem: B)= new DoubleDeck"""+name+"""[B](new """+name+"""1[B](elem),this);
	    def head: A= _1;
	    def tail:"""+name+(size-1)+"""[A] = new """+name+(size-1)+"("+fields.drop(1).take(size-1).mkString(",")+""");
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="N";

	    override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => {
			      """+ fields.take(size).mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + """+ fields.take(size).mkString("+") + """ 
			      }
	                      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      } //N
		 
""");
for (j<-2 to size-1){

println("""
      final private val """+name+"F"+j+":Array[Function1["+name+j+"[_],_]]=Array"+
	fields.take(j).map{s => "(x:"+name+j+"[_]) => x."+s}.mkString("({","}, {","});")+"""
      final private val """+name+"F"+j+"Reversed:Array[Function1["+name+j+"[_],_]]="+name+"F"+j+""".reverse;

      final """+caseModifier+""" class """+name+j+"[+a]"+fields.take(j).mkString("(val ",":a, val ",":a)")+""" extends SmallDeck[a] {

	    def apply(n:Int):a= """++name+"F"+j +"""(n).asInstanceOf[a];
	    def elements="""++name+"F"+j+""".elements.map{f => f(this).asInstanceOf[a]};
	    def reverseElements="""++name+"F"+j+"""Reversed.elements.map{f => f(this).asInstanceOf[a]};
		  
	    def length="""+j+""";
	    override def isEmpty=false;
	    
	    def +[b >: a](elem: b)= new """+name+(j+1)+"("+fields.take(j).mkString(",")+""",elem);

	    def peek:a= """+fields(j-1)+""";
	    def pop= new """+name+(j-1)+"("+fields.take(j-1).mkString(",")+""");

	    def ::[b >: a](elem: b)= new """+name+(j+1)+"(elem,"+fields.take(j).mkString(",")+""");
	    def head: a= _1;
	    def tail:"""+name+(j-1)+"""[a] = new """+name+(j-1)+"("+fields.drop(1).take(j-1).mkString(",")+""");
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: a](that:Seq[B]): Deck[B] = {
		  that match {
			case other:EmptyDeck => this;
			case other:Deck[B] => {
			      """+ fields.take(j).mkString(" :: ") + """ :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: a](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + """+ fields.take(j).mkString("+") + """ 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n
""");
}

println("""
      final case class DoubleDeck"""+name+"""[+A](front:Deck[A],back:Deck[A]) extends Deck[A] {
	    type DoubleDeck[+T]= DoubleDeck"""+name+"""[T];
	    type TripleDeck[+T]= TripleDeck"""+name+"""[T];
	    type SingletonDeck[+T]= """+name+"""1[T];
	    final private val EmptyDeck= Empty"""+name+""";

	    def apply(n: Int): A={
		  if (n<front.length){
			front.apply(n);
		  } else {
			back.apply(n-front.length);
		  }
	    }
	    
	    def elements: Iterator[A]= front.elements ++ back.elements;
	    def reverseElements: Iterator[A]= back.reverseElements ++ front.reverseElements;
	    override def isEmpty: Boolean= false;
	    def length:Int=front.length + back.length;

	    def +[B >: A](elem: B):Deck[B]={
		  if (back.length=="""+size+"""){
			new TripleDeck(length+1,front,new SingletonDeck(back),new SingletonDeck(elem)); //k
		  } else {
			new DoubleDeck(front,back.push(elem)); //k
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={ 
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			front;
		  } else {
			new DoubleDeck(front,postpop);
		  }
	    }
	    def ::[B >: A](elem: B):Deck[B]={
		  if (front.length=="""+size+"""){
			new TripleDeck(length+1,new SingletonDeck(elem),new SingletonDeck(front),back); //k
		  } else {
			new DoubleDeck(front.unshift(elem),back); //k
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val posttail=front.tail;
		  if (posttail.isEmpty){
			back;
		  } else {
			new DoubleDeck(posttail,back); //k
		  }
	    }

	    def nodes=1+front.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  1+ (if (fd>bd) fd else bd)
	    }
	    def state="["+front.state+","+back.state+"]";
	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  
		  that match{
			case EmptyDeck => this;
		       
			case _ => { // not optimized
			      throw new Error("Not yet supported:  "+that.getClass); // shouldn't be called yet. fixme			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    } // end :::
      } // DoubleDeck

      // none of these subdeques are empty
      final case class TripleDeck"""+name+"""[+A](N:Int,front:Deck[A],up:Deck[Deck[A]],back:Deck[A]) extends Deck[A] {
	    type DoubleDeck[+T]= DoubleDeck"""+name+"""[T];
	    type TripleDeck[+T]= TripleDeck"""+name+"""[T];
	    type SingletonDeck[+T]= """+name+"""1[T];
	    final private val EmptyDeck= Empty"""+name+""";
	    
	    // slow.
	    def apply(n: Int): A= elements.drop(n).next();
	    
	    // does Iterator.flatten make them less lazy?  Its best if they are not wasting memory.
	    def elements: Iterator[A]= front.elements ++ Iterator.flatten(up.map(_.elements).elements) ++ back.elements;
	    // this looks buggy, is It?
	    def reverseElements: Iterator[A]= {back.reverseElements ++ 
					       Iterator.flatten(up.reverseElements.map(_.reverseElements))++
					       front.reverseElements;}
	    override def isEmpty: Boolean= false;
	    def length:Int=N;
	    
	    def +[B >: A](elem: B):Deck[B]={
		  if (back.length=="""+size+"""){
			new TripleDeck(N+1,front,up.push(back),new SingletonDeck(elem));
		  } else {
			new TripleDeck(N+1,front,up,back.push(elem));
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={
		  val postpop=back.pop;
		  if (postpop.isEmpty){
			val uppop=up.pop;
			if (uppop.isEmpty){
			      new DoubleDeck(front,up.peek); 
			} else {
			      new TripleDeck(N-1,front, uppop, up.peek); 
			}
		  } else {
			new TripleDeck(N-1,front,up,postpop); 
		  }
	    }
	    
	    def ::[B >: A](elem: B):Deck[B]={
		  if (front.length=="""+size+"""){
			new TripleDeck(N+1,new SingletonDeck(elem),up.unshift(front),back);
		  } else {
			new TripleDeck(N+1,front.unshift(elem),up,back);
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val fronttail=front.tail;
		  if (fronttail.isEmpty){
			val uptail=up.tail;
			if (uptail.isEmpty){
			      new DoubleDeck(up.head,back)
			} else {
			      new TripleDeck(N-1,up.head,uptail,back);
			}
		  } else {
			new TripleDeck(N-1,fronttail,up,back);
		  }
	    }
	    def nodes=1+front.nodes+up.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  val mfb=if (fd>bd) fd else bd;
		  val ud=up.depth;
		  1+ (if (ud>mfb) ud else mfb);
	    }
	    def state="("+front.state+","+up.state+","+back.state+")";


	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case EmptyDeck => this;
			case other:SmallDeck[_] =>{
			      (other.asInstanceOf[Deck[B]] :\ this.asInstanceOf[Deck[B]]){case (e,d) => e::d}
			}
			case that:Deque[B] => { // not optimized
			      throw new Error("Not yet supported:  "+that.getClass); // shouldn't be called yet. fixme
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

      }// end TripleDeck


""");

} // fnodes

println("""
	
      sealed abstract class EmptyDeck extends Deck[Nothing]{
	    def :::[B](that:Deque[B]): Deck[B] = {
		  that match {
			case other:Deck[B] =>
			      other;
			case _ => {
			      throw new Error("Not yet supported");
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    }
	    override def ++[B](that:Seq[B]):Deck[B]={	
		  that match {
			case other:Deck[B] =>
			      other;
			case _ => {
			      throw new Error("Not yet supported");
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    }
      }

      sealed trait SmallDeck[+A] extends Deck[A]{  
      } //small deck

      sealed abstract class Deck[+A] extends Deque[A] with Seq[A]{

	    def apply(n: Int): A;
	    
	    def elements: Iterator[A];
	    def reverseElements: Iterator[A];
	    def reverseDeque:Deque[A]=ReverseDeque(this);
	    def isEmpty: Boolean;
	    def length:Int;

	    def push[B >: A](elem: B):Deck[B]= this +elem;
	    def peek:A;
	    def pop:Deck[A];
	    
	    def unshift[B >: A](elem: B):Deck[B] = elem ::this;
	    def head: A;
	    def tail: Deck[A];

	    override def equals(o: Any): Boolean={
		  o match {
			case d:Deck[_] => {
			      length==d.length && elements.zip(d.elements).forall{case (a,b) => a==b};
			}
			case _ => false;
		  }
	    }
	    override def hashCode(): Int={
		  (0 /: elements){case (i,a) => i ^ a.hashCode}
	    }

	    def dequeue: (A, Deck[A])=(head,tail);
	    def ::[B >: A](elem: B):Deck[B];
	    def shift: Deck[A]=tail;    
	    def enqueue[B >: A](elem: B):Deck[B]=push(elem);
	    def +[B >: A](elem: B):Deck[B];
	    def peekPop: (A, Deck[A])=(peek,pop);

	    override def ++[B >: A](s:Seq[B]): Deck[B] = {
		  (s) match {
			case that:Deck[B] => this ::: that;
			case s => { 
			      throw new Error("Not yet supported");
			      val thisB:Deck[B]=this;
			      (thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B];

	    override def foldRight[B](z: B)(op: (A, B) => B): B = {
		  var acc:B = z
		  val i=reverseElements;
	          while (i.hasNext) acc = op(i.next,acc);
	          acc
            }

      }
}
""");

